package com.cb2.algorithm.leetcode;

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

/**
 * <a href="https://leetcode.cn/problems/leaf-similar-trees">叶子相似的树(Leaf-Similar Trees)</a>
 * <p>请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。</p>
 * <pre>
 *                   3
 *                /     \
 *               5       1
 *              / \     / \
 *             <a color="blue">6</a>   2   <a color="blue">9</a>   <a color="blue">8</a>
 *                / \
 *               <a color="blue">7</a>   <a color="blue">4</a>
 * 举个例子，如上图所示，给定一棵叶值序列为 (6, 7, 4, 9, 8) 的树。
 * </pre>
 * <p>如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。
 * <p>
 * 如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。
 * </p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
 *                  3                               3
 *               /     \                         /     \
 *              5       1                       5       1
 *             / \     / \                     / \     / \
 *            6   2   9   8                   6   7   4   2
 *               / \                                     / \
 *              7   4                                   9   8
 *      输出：true
 *
 * 示例 2：
 *      输入：root1 = [1,2,3], root2 = [1,3,2]
 *                  1                   1
 *                 / \                 / \
 *                2   3               3   2
 *      输出：false
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>给定的两棵树结点数在 [1, 200] 范围内</li>
 *     <li>给定的两棵树上的值在 [0, 200] 范围内</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/5/25 14:23
 */
public class LC0872LeafSimilar_S {
    static class Solution {
        public boolean leafSimilar(TreeNode root1, TreeNode root2) {
            List<Integer> list1 = new ArrayList<>();
            dfs(root1, list1);
            List<Integer> list2 = new ArrayList<>();
            dfs(root2, list2);

            if (list1.size() == list2.size()) {
                for (int i = 0; i < list1.size(); i++) {
                    if (!Objects.equals(list1.get(i), list2.get(i))) {
                        return false;
                    }
                }
                return true;
            }
            return false;
        }

        private void dfs(TreeNode currNode, List<Integer> list) {
            if (currNode == null) {
                return;
            }
            if (currNode.left == null && currNode.right == null) {
                list.add(currNode.val);
                return;
            }
            dfs(currNode.left, list);
            dfs(currNode.right, list);
        }

        public static void main(String[] args) {

            Solution solution = new Solution();

            //TreeNode root1 = new TreeNode(1);
            //root1.left = new TreeNode(2);
            //root1.right = new TreeNode(3);
            //TreeNode root2 = new TreeNode(1);
            //root2.left = new TreeNode(3);
            //root2.right = new TreeNode(2);
            //System.out.println(solution.leafSimilar(root1, root2));


            TreeNode root3 = new TreeNode(3);
            root3.left = new TreeNode(5);
            root3.left.left = new TreeNode(6);
            root3.left.right = new TreeNode(2);
            root3.left.right.left = new TreeNode(7);
            root3.left.right.right = new TreeNode(4);
            root3.right = new TreeNode(1);
            root3.right.left = new TreeNode(9);
            root3.right.right = new TreeNode(8);
            Printer.printTreeNode(root3);

            TreeNode root4 = new TreeNode(3);
            root4.left = new TreeNode(5);
            root4.left.left = new TreeNode(6);
            root4.left.right = new TreeNode(7);
            root4.right = new TreeNode(1);
            root4.right.left = new TreeNode(4);
            root4.right.right = new TreeNode(2);
            root4.right.right.left = new TreeNode(9);
            root4.right.right.right = new TreeNode(8);
            Printer.printTreeNode(root4);

            System.out.println(solution.leafSimilar(root3, root4));
        }
    }
}